#include "string_array.h"
#include<iostream>
#include<cstring>
#include <vector>
#include <algorithm>
using namespace std;

void myStr::print()
{
    for(int i = 0; i < this->length; i++)
    {
        cout << this->data[i];
    }
    cout << endl;
}

myStr::myStr(const char* str)//字符串初始化
{
    length = strlen(str);
    data =new char[length+1];
    strcpy(data,str);
    next=new int [length];
    nextVal=new int [length];
}

myStr::~myStr()//字符串销毁
{   
    delete[] nextVal;
    delete[] next;
    delete[] data;
}

void myStr::kmp_next()//next
{
    int i=1;
    int* temper;

    temper=new int [length+1]; //临时构建一个数组，用于从1开始存储计算出的next值

    temper[0]=0;//或许不必要？？？？
    temper[1]=0;

    int j=0;

    while(i<length+1)
    {
        if(j==0||data[i-1]==data[j-1])
        {
            ++i;
            ++j;
            temper[i]=j;
        }
        else
        {
            j=temper[j];
        }
    }

    for(int i=0;i<length;i++)
    {
        next[i]=temper[i+1];
    }
}
//仿照课件的思路，但是课件上字符串的第一位存的是字符串的长度，next数组从1开始存取数据，而这里字符串第一位就是字符串的内容，next数组从0开始存取，所以临时构造了一个数组，最后依次减一赋值，得到next数组

void myStr::kmp_nextVal()//nextval是next的进一步改良
{
    int i=1;
    int* temper;

    temper=new int [length+1]; //这里同求next数组，临时构建一个数组，用于从1开始存储计算出的next值
    temper[0]=0;
    temper[1]=0;

    int j=0;
    while(i<length+1)
    {
        if(j == 0 || data[i-1]==data[j-1])
        {
            i++;
            j++;
            if(data[i-1]!=data[j-1])
            {
                temper[i]=j;
            }
            else
            {
                temper[i]=temper[j];
            }
        }
        else
        {
            j=temper[j];
        }
    }

    for(int i=0;i<length;i++)
    {
        nextVal[i]=temper[i+1];
    }
}

void myStr::printNext()
{
    for(int i = 0; i < length; i++)
    {
        cout << next[i];
    }
    cout << endl;
}

void myStr::printNextVal()
{
    for(int i = 0; i < length; i++)
    {
        cout << nextVal[i];
    }
    cout << endl;
}



bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)
//替换字符串
{
    int sLength = S.length;
    int tLength = T.length;
    
    if (start < 1 || start > sLength) 
    {
        return 0;
    }

    for (int i = start - 1; i <= sLength - tLength; i++) 
    {
        if (strncmp(S.data + i, T.data, tLength) == 0) //比较是否相等
        {
            // 替换
            char* newData = new char[sLength - tLength + V.length + 1];
            strncpy(newData, S.data, i);
            strcpy(newData + i, V.data);
            strcpy(newData + i + V.length, S.data + i + tLength);
            
            delete[] S.data;
            S.data = newData;
            S.length = sLength - tLength + V.length;
            return 1;
        }
    }
    return 0;
}

int kmpMatch(const myStr& S, const myStr& T){
     int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.data[i - 1] == T.data[j - 1])
        {
            i++;
            j++;
        }
        else
            j = T.next[j - 1];
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    return -1;
}

int simpleMatch(const myStr& S, const myStr& T)
{
    int i=0;
    int j=0;
    while(i<S.length&&j<T.length)//简单匹配，依次比较是否相等
    {
        if(S.data[i]==T.data[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j==T.length)//模式串全部匹配
    {
        return i-T.length+1; //字符串位置从1开始计数
    }
    else
    {
        return -1;
    }

}

myMatrix::myMatrix() //构造一个空的稀疏矩阵
{
    rowNum=0;
    colNum=0;
    nodeNum=0;
    nodeList=nullptr;
}


bool compare(matrixNode a,matrixNode b)//用于sort的比较函数
{
    if(a.row!=b.row)
    {
        return a.row<b.row;
    }
    return a.col<b.col;
}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* n)//参数依次为行数、列数、三元组元素个数、三元组初始化数据，数组元素为3的倍数，每3个数一组，分别为（row，col，value）
{
    rowNum=rNum;
    colNum=cNum;
    nodeNum=nNum;
    nodeList=new matrixNode[nNum];
    for(int i=0,p=0;i<3*nNum;i=i+3,p++)
    {
        nodeList[p].row=n[i];
        nodeList[p].col=n[i+1];
        nodeList[p].value=n[i+2];
    }
    sort(nodeList,nodeList+nodeNum,compare);//按行排序
}
myMatrix:: ~myMatrix()//销毁矩阵
{
    delete[] nodeList;
}

void myMatrix::FastTransposeSMatrix(myMatrix& T) //快速转置
{
    T.rowNum = colNum;  
    T.colNum = rowNum;  
    T.nodeNum = nodeNum;  
    T.nodeList = new matrixNode[nodeNum];
    int* num = new int[colNum];
    int* cpot = new int[colNum];
    if(T.nodeNum)
    {
        for(int i=0;i<colNum;i++)//初始化数组
        {
            num[i]=0;
            cpot[i]=0;
        }
        
        for(int j=0;j < nodeNum ; j++)//求第j列非零元素的个数
        {
            num[nodeList[j].col]++;
        }

        for(int x=1;x<colNum;x++)//求各列第一个非零元素在转置矩阵中的位置
        {
            cpot[x]=cpot[x-1]+num[x-1];
        }

        for(int m=0;m<nodeNum;m++)
        {
            int lie=nodeList[m].col;
            int ddd=cpot[lie];
            T.nodeList[ddd].row=nodeList[m].col;
            T.nodeList[ddd].col=nodeList[m].row;
            T.nodeList[ddd].value=nodeList[m].value;
            cpot[lie]++;//如果该列有多个非零元素，则指向下一个元素应在的位置
        }
    }
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;
    for(int i = 0; i < nodeNum; i++)
    {
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
    }
}